﻿// -------------------------------------------------------------------------
//    @FileName         :    TestNFShmHashMultiSetWithListAdvanced.h
//    @Author           :    gaoyi
//    @Date             :    2024-01-20
//    @Email			:    445267987@qq.com
//    @Module           :    TestNFShmHashMultiSetWithListAdvanced
//
// -------------------------------------------------------------------------

#pragma once

#include "NFComm/NFShmStl/NFShmHashMultiSetWithList.h"
#include <gtest/gtest.h>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <chrono>
#include <random>

/**
 * @file TestNFShmHashMultiSetWithListAdvanced.h
 * @brief NFShmHashMultiSetWithList 高级链表排序接口的单元测试
 * 
 * 本文件专门测试多重集合容器的以下高级接口：
 * 1. insert_list_sorted() - 按有序位置插入元素（允许重复）
 * 2. emplace_list_sorted() - 原地构造并按有序位置插入
 * 3. emplace_hint_list_sorted() - 带提示的原地构造并按有序位置插入
 * 4. move_to_list_node_front() - 将节点移到链表前端
 * 5. move_to_list_node_back() - 将节点移到链表后端
 * 6. move_to_list_sorted() - 将节点移到正确的有序位置
 * 
 * 特别关注MultiSet容器的特性：
 * - 允许重复元素
 * - 相同元素的相邻性
 * - 基于值的排序
 * - count和equal_range的有效性
 */

// 测试用的评分记录
struct RatingRecord
{
    double score;
    std::string reviewer;
    std::string category;

    RatingRecord() : score(0.0)
    {
    }

    RatingRecord(double s, const std::string& r, const std::string& c) : score(s), reviewer(r), category(c)
    {
    }

    bool operator==(const RatingRecord& other) const
    {
        return score == other.score && reviewer == other.reviewer && category == other.category;
    }

    bool operator<(const RatingRecord& other) const
    {
        if (score != other.score)
            return score < other.score;
        if (category != other.category)
            return category < other.category;
        return reviewer < other.reviewer;
    }
};

// RatingRecord的哈希函数
namespace std
{
    template <>
    struct hash<RatingRecord>
    {
        size_t operator()(const RatingRecord& r) const
        {
            return std::hash<double>{}(r.score) ^ (std::hash<std::string>{}(r.reviewer) << 1) ^ (std::hash<std::string>{}(r.category) << 2);
        }
    };
}

/**
 * @brief 测试MultiSet的insert_list_sorted接口
 */
TEST(NFShmHashMultiSetWithListAdvancedTest, InsertListSorted)
{
    printf("========== MultiSet InsertListSorted Test ==========\n");

    NFShmHashMultiSetWithList<int, 100> numberMultiSet;
    numberMultiSet.CreateInit();

    // 测试1：使用默认比较器插入重复数字
    printf("Test 1: Insert duplicate numbers with default comparator\n");

    auto it1 = numberMultiSet.insert_list_sorted(85);
    EXPECT_EQ(*it1, 85);

    auto it2 = numberMultiSet.insert_list_sorted(92);
    EXPECT_EQ(*it2, 92);

    auto it3 = numberMultiSet.insert_list_sorted(85); // 重复的85
    EXPECT_EQ(*it3, 85);

    auto it4 = numberMultiSet.insert_list_sorted(78);
    EXPECT_EQ(*it4, 78);

    auto it5 = numberMultiSet.insert_list_sorted(92); // 重复的92
    EXPECT_EQ(*it5, 92);

    auto it6 = numberMultiSet.insert_list_sorted(89);
    EXPECT_EQ(*it6, 89);

    printf("After insert_list_sorted (should be sorted, allowing duplicates):\n");
    std::vector<int> values;
    for (auto it = numberMultiSet.list_begin(); it != numberMultiSet.list_end(); ++it)
    {
        printf("  %d\n", *it);
        values.push_back(*it);
    }

    // 验证按value升序排列
    EXPECT_TRUE(std::is_sorted(values.begin(), values.end()));
    std::vector<int> expected_values = {78, 85, 85, 89, 92, 92};
    EXPECT_EQ(values, expected_values);

    // 验证重复计数
    EXPECT_EQ(numberMultiSet.size(), 6);
    EXPECT_EQ(numberMultiSet.count(85), 2);
    EXPECT_EQ(numberMultiSet.count(92), 2);
    EXPECT_EQ(numberMultiSet.count(78), 1);
    EXPECT_EQ(numberMultiSet.count(89), 1);

    numberMultiSet.clear();

    // 测试2：使用自定义比较器（降序）
    printf("\nTest 2: Custom comparator (descending)\n");

    auto comp = [](const int& a, const int& b) { return a > b; };

    numberMultiSet.insert_list_sorted(85, comp);
    numberMultiSet.insert_list_sorted(92, comp);
    numberMultiSet.insert_list_sorted(85, comp); // 重复
    numberMultiSet.insert_list_sorted(78, comp);
    numberMultiSet.insert_list_sorted(89, comp);

    printf("After insert_list_sorted with descending comparator:\n");
    std::vector<int> desc_values;
    for (auto it = numberMultiSet.list_begin(); it != numberMultiSet.list_end(); ++it)
    {
        printf("  %d\n", *it);
        desc_values.push_back(*it);
    }

    // 验证按value降序排列
    EXPECT_TRUE(std::is_sorted(desc_values.begin(), desc_values.end(), std::greater<int>()));
    std::vector<int> expected_desc_values = {92, 89, 85, 85, 78};
    EXPECT_EQ(desc_values, expected_desc_values);

    printf("MultiSet InsertListSorted test passed\n");
}

/**
 * @brief 测试MultiSet的emplace_list_sorted接口
 */
TEST(NFShmHashMultiSetWithListAdvancedTest, EmplaceListSorted)
{
    printf("========== MultiSet EmplaceListSorted Test ==========\n");

    NFShmHashMultiSetWithList<RatingRecord, 100> ratingMultiSet;
    ratingMultiSet.CreateInit();

    // 测试1：使用默认比较器原地构造评分记录
    printf("Test 1: Emplace rating records with default comparator\n");

    auto it1 = ratingMultiSet.emplace_list_sorted(4.5, "Alice", "Design");
    EXPECT_EQ(it1->score, 4.5);

    auto it2 = ratingMultiSet.emplace_list_sorted(3.8, "Bob", "Performance");
    EXPECT_EQ(it2->score, 3.8);

    auto it3 = ratingMultiSet.emplace_list_sorted(4.5, "Charlie", "Design"); // 相同分数，不同reviewer
    EXPECT_EQ(it3->score, 4.5);

    auto it4 = ratingMultiSet.emplace_list_sorted(4.2, "David", "Usability");
    EXPECT_EQ(it4->score, 4.2);

    auto it5 = ratingMultiSet.emplace_list_sorted(3.8, "Eve", "Performance"); // 相同分数和category
    EXPECT_EQ(it5->score, 3.8);

    printf("After emplace_list_sorted (should be sorted by score, then category, then reviewer):\n");
    std::vector<double> scores;
    for (auto it = ratingMultiSet.list_begin(); it != ratingMultiSet.list_end(); ++it)
    {
        printf("  Score:%.1f by %s (%s)\n", it->score, it->reviewer.c_str(), it->category.c_str());
        scores.push_back(it->score);
    }

    // 验证按score升序排列
    EXPECT_TRUE(std::is_sorted(scores.begin(), scores.end()));
    EXPECT_EQ(ratingMultiSet.size(), 5);
    EXPECT_EQ(ratingMultiSet.count(RatingRecord(4.5, "Alice", "Design")), 1);
    EXPECT_EQ(ratingMultiSet.count(RatingRecord(3.8, "Bob", "Performance")), 1);

    ratingMultiSet.clear();

    // 测试2：使用自定义比较器（仅按分数降序，忽略其他字段）
    printf("\nTest 2: Custom comparator (by score desc only)\n");

    auto comp = [](const RatingRecord& a, const RatingRecord& b)
    {
        return a.score > b.score;
    };

    ratingMultiSet.emplace_list_sorted_comp(comp, 4.5, "Alice", "Design");
    ratingMultiSet.emplace_list_sorted_comp(comp, 3.8, "Bob", "Performance");
    ratingMultiSet.emplace_list_sorted_comp(comp, 4.5, "Charlie", "Usability"); // 相同分数
    ratingMultiSet.emplace_list_sorted_comp(comp, 4.2, "David", "Design");
    ratingMultiSet.emplace_list_sorted_comp(comp, 4.5, "Eve", "Performance"); // 又一个相同分数

    printf("After emplace_list_sorted with score-only descending comparator:\n");
    for (auto it = ratingMultiSet.list_begin(); it != ratingMultiSet.list_end(); ++it)
    {
        printf("  Score:%.1f by %s (%s)\n", it->score, it->reviewer.c_str(), it->category.c_str());
    }

    // 验证分数按降序排列
    std::vector<double> desc_scores;
    for (auto it = ratingMultiSet.list_begin(); it != ratingMultiSet.list_end(); ++it)
    {
        desc_scores.push_back(it->score);
    }
    EXPECT_TRUE(std::is_sorted(desc_scores.begin(), desc_scores.end(), std::greater<double>()));

    printf("MultiSet EmplaceListSorted test passed\n");
}

/**
 * @brief 测试MultiSet的emplace_hint_list_sorted接口
 */
TEST(NFShmHashMultiSetWithListAdvancedTest, EmplaceHintListSorted)
{
    printf("========== MultiSet EmplaceHintListSorted Test ==========\n");

    NFShmHashMultiSetWithList<std::string, 100> tagMultiSet;
    tagMultiSet.CreateInit();

    // 测试：emplace_hint_list_sorted应该忽略hint参数，维持正确排序
    printf("Test: emplace_hint_list_sorted should maintain correct order with duplicates\n");

    auto it1 = tagMultiSet.emplace_hint_list_sorted("urgent");
    EXPECT_EQ(*it1, "urgent");

    auto it2 = tagMultiSet.emplace_hint_list_sorted("important");
    EXPECT_EQ(*it2, "important");

    auto it3 = tagMultiSet.emplace_hint_list_sorted("urgent"); // 重复
    EXPECT_EQ(*it3, "urgent");

    auto it4 = tagMultiSet.emplace_hint_list_sorted("normal");
    EXPECT_EQ(*it4, "normal");

    auto it5 = tagMultiSet.emplace_hint_list_sorted("important"); // 重复
    EXPECT_EQ(*it5, "important");

    auto it6 = tagMultiSet.emplace_hint_list_sorted("low");
    EXPECT_EQ(*it6, "low");

    printf("After emplace_hint_list_sorted:\n");
    std::vector<std::string> tags;
    for (auto it = tagMultiSet.list_begin(); it != tagMultiSet.list_end(); ++it)
    {
        printf("  %s\n", it->c_str());
        tags.push_back(*it);
    }

    // 验证按字母升序排列
    EXPECT_TRUE(std::is_sorted(tags.begin(), tags.end()));
    std::vector<std::string> expected_tags = {"important", "important", "low", "normal", "urgent", "urgent"};
    EXPECT_EQ(tags, expected_tags);

    // 验证重复计数
    EXPECT_EQ(tagMultiSet.count("urgent"), 2);
    EXPECT_EQ(tagMultiSet.count("important"), 2);
    EXPECT_EQ(tagMultiSet.count("normal"), 1);
    EXPECT_EQ(tagMultiSet.count("low"), 1);

    printf("MultiSet EmplaceHintListSorted test passed\n");
}

/**
 * @brief 测试MultiSet的move_to_list_node_front接口
 */
TEST(NFShmHashMultiSetWithListAdvancedTest, MoveToListNodeFront)
{
    printf("========== MultiSet MoveToListNodeFront Test ==========\n");

    NFShmHashMultiSetWithList<int, 100> numberMultiSet;
    numberMultiSet.CreateInit();

    // 插入重复数据并排序
    numberMultiSet.insert(85);
    numberMultiSet.insert(92);
    numberMultiSet.insert(85); // 重复
    numberMultiSet.insert(78);
    numberMultiSet.insert(89);
    numberMultiSet.insert(92); // 重复
    numberMultiSet.sort_list(); // 按value升序排序

    printf("Original sorted order with duplicates:\n");
    for (auto it = numberMultiSet.list_begin(); it != numberMultiSet.list_end(); ++it)
    {
        printf("  %d\n", *it);
    }

    // 测试1：移动某个特定的重复元素到前端
    printf("\nTest 1: Move specific duplicate element to front\n");

    // 找到第二个85
    auto it = numberMultiSet.list_begin();
    ++it; // 跳过第一个78，现在指向第一个85
    ++it; // 现在指向第二个85
    EXPECT_EQ(*it, 85);

    numberMultiSet.move_to_list_node_front(it);

    printf("After moving second 85 to front:\n");
    for (auto it = numberMultiSet.list_begin(); it != numberMultiSet.list_end(); ++it)
    {
        printf("  %d\n", *it);
    }

    // 测试2：使用自定义比较器
    printf("\nTest 2: Move with custom comparator\n");

    auto comp = [](const int& a, const int& b) { return a > b; };
    auto target_it = numberMultiSet.find(92);
    numberMultiSet.move_to_list_node_front(target_it, comp);

    printf("After moving 92 to front with descending comparator:\n");
    for (auto it = numberMultiSet.list_begin(); it != numberMultiSet.list_end(); ++it)
    {
        printf("  %d\n", *it);
    }

    // 验证重复元素计数
    EXPECT_EQ(numberMultiSet.count(85), 2);
    EXPECT_EQ(numberMultiSet.count(92), 2);
    EXPECT_EQ(numberMultiSet.size(), 6);

    printf("MultiSet MoveToListNodeFront test passed\n");
}

/**
 * @brief 测试MultiSet的move_to_list_node_back接口
 */
TEST(NFShmHashMultiSetWithListAdvancedTest, MoveToListNodeBack)
{
    printf("========== MultiSet MoveToListNodeBack Test ==========\n");

    NFShmHashMultiSetWithList<int, 100> numberMultiSet;
    numberMultiSet.CreateInit();

    // 插入重复数据并排序
    numberMultiSet.insert(85);
    numberMultiSet.insert(92);
    numberMultiSet.insert(85); // 重复
    numberMultiSet.insert(78);
    numberMultiSet.insert(89);
    numberMultiSet.insert(92); // 重复
    numberMultiSet.sort_list(); // 按value升序排序

    printf("Original sorted order with duplicates:\n");
    for (auto it = numberMultiSet.list_begin(); it != numberMultiSet.list_end(); ++it)
    {
        printf("  %d\n", *it);
    }

    // 测试1：移动某个特定的重复元素到后端
    printf("\nTest 1: Move specific duplicate element to back\n");

    // 找到第一个92
    auto target_it = numberMultiSet.find(92);
    EXPECT_EQ(*target_it, 92);

    numberMultiSet.move_to_list_node_back(target_it);

    printf("After moving first 92 to back:\n");
    for (auto it = numberMultiSet.list_begin(); it != numberMultiSet.list_end(); ++it)
    {
        printf("  %d\n", *it);
    }

    // 测试2：使用链表迭代器
    printf("\nTest 2: Move using list_iterator\n");

    auto list_it = numberMultiSet.list_begin();
    ++list_it; // 指向第二个元素
    numberMultiSet.move_to_list_node_back(list_it);

    printf("After moving second element to back:\n");
    for (auto it = numberMultiSet.list_begin(); it != numberMultiSet.list_end(); ++it)
    {
        printf("  %d\n", *it);
    }

    // 验证多重集合的统计
    EXPECT_EQ(numberMultiSet.count(85), 2);
    EXPECT_EQ(numberMultiSet.count(92), 2);
    EXPECT_EQ(numberMultiSet.count(78), 1);
    EXPECT_EQ(numberMultiSet.count(89), 1);
    EXPECT_EQ(numberMultiSet.size(), 6);

    printf("MultiSet MoveToListNodeBack test passed\n");
}

/**
 * @brief 综合测试：多重集合特有的场景和性能测试
 */
TEST(NFShmHashMultiSetWithListAdvancedTest, MultiSetSpecificScenarios)
{
    printf("========== MultiSet Specific Scenarios Test ==========\n");

    // 测试1：大量重复元素的处理
    printf("Test 1: Handle many duplicate elements\n");
    {
        NFShmHashMultiSetWithList<int, 100> manyDupMultiSet;
        manyDupMultiSet.CreateInit();

        // 插入大量重复数据
        std::vector<int> test_data = {5, 3, 5, 8, 3, 5, 1, 8, 5, 9, 1, 5, 3, 7, 8};

        for (int val : test_data)
        {
            manyDupMultiSet.insert_list_sorted(val);
        }

        printf("After inserting %d elements (with duplicates):\n", (int)test_data.size());
        std::vector<int> sorted_values;
        for (auto it = manyDupMultiSet.list_begin(); it != manyDupMultiSet.list_end(); ++it)
        {
            printf("  %d\n", *it);
            sorted_values.push_back(*it);
        }

        // 验证排序正确性
        EXPECT_TRUE(std::is_sorted(sorted_values.begin(), sorted_values.end()));
        EXPECT_EQ(manyDupMultiSet.size(), test_data.size());

        // 验证重复计数
        std::multiset<int> expected_multiset(test_data.begin(), test_data.end());
        for (auto it = expected_multiset.begin(); it != expected_multiset.end(); it = expected_multiset.upper_bound(*it))
        {
            int value = *it;
            size_t expected_count = expected_multiset.count(value);
            size_t actual_count = manyDupMultiSet.count(value);
            EXPECT_EQ(actual_count, expected_count);
            printf("  Value %d appears %zu times\n", value, actual_count);
        }
    }

    // 测试2：混合操作场景
    printf("\nTest 2: Mixed operations scenario\n");
    {
        NFShmHashMultiSetWithList<double, 50> mixedMultiSet;
        mixedMultiSet.CreateInit();

        // 使用不同接口插入数据
        mixedMultiSet.insert_list_sorted(3.5);
        mixedMultiSet.emplace_list_sorted(2.8);
        mixedMultiSet.insert_list_sorted(3.5); // 重复
        mixedMultiSet.emplace_hint_list_sorted(4.2);
        mixedMultiSet.emplace_list_sorted(2.8); // 重复

        printf("After mixed insertions:\n");
        for (auto it = mixedMultiSet.list_begin(); it != mixedMultiSet.list_end(); ++it)
        {
            printf("  %.1f\n", *it);
        }

        // 移动操作
        auto it_to_move = mixedMultiSet.find(4.2);
        mixedMultiSet.move_to_list_sorted(it_to_move);

        printf("\nAfter move operation:\n");
        std::vector<double> values;
        for (auto it = mixedMultiSet.list_begin(); it != mixedMultiSet.list_end(); ++it)
        {
            printf("  %.1f\n", *it);
            values.push_back(*it);
        }

        // 验证排序
        EXPECT_TRUE(std::is_sorted(values.begin(), values.end()));
        EXPECT_EQ(mixedMultiSet.count(3.5), 2);
        EXPECT_EQ(mixedMultiSet.count(2.8), 2);
        EXPECT_EQ(mixedMultiSet.count(4.2), 1);
    }

    // 测试3：性能测试
    printf("\nTest 3: Performance test with duplicates\n");
    {
        const int TEST_SIZE = 300;
        NFShmHashMultiSetWithList<int, TEST_SIZE> perfMultiSet;
        perfMultiSet.CreateInit();

        // 生成包含重复的随机数据
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<> value_dist(1, 50); // 50个不同的值，会有大量重复

        std::vector<int> test_values;
        for (int i = 0; i < TEST_SIZE; ++i)
        {
            test_values.push_back(value_dist(gen));
        }

        auto start = std::chrono::high_resolution_clock::now();
        for (int value : test_values)
        {
            perfMultiSet.insert_list_sorted(value);
        }
        auto end = std::chrono::high_resolution_clock::now();
        auto insert_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

        printf("insert_list_sorted %d elements (with duplicates) took %lld microseconds\n", TEST_SIZE, insert_time.count());

        // 验证排序正确性
        std::vector<int> all_values;
        for (auto it = perfMultiSet.list_begin(); it != perfMultiSet.list_end(); ++it)
        {
            all_values.push_back(*it);
        }
        EXPECT_TRUE(std::is_sorted(all_values.begin(), all_values.end()));
        EXPECT_EQ(perfMultiSet.size(), TEST_SIZE);

        // 验证重复计数正确性
        std::multiset<int> expected_multiset(test_values.begin(), test_values.end());
        for (int value = 1; value <= 50; ++value)
        {
            size_t expected_count = expected_multiset.count(value);
            size_t actual_count = perfMultiSet.count(value);
            EXPECT_EQ(actual_count, expected_count);
        }

        // 测试move操作性能
        start = std::chrono::high_resolution_clock::now();
        for (int i = 0; i < 30; ++i) // 移动30个元素
        {
            auto it = perfMultiSet.find(i % 50 + 1);
            if (it != perfMultiSet.end())
            {
                perfMultiSet.move_to_list_sorted(it);
            }
        }
        end = std::chrono::high_resolution_clock::now();
        auto move_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

        printf("move_to_list_sorted 30 elements took %lld microseconds\n", move_time.count());

        // 再次验证排序正确性
        all_values.clear();
        for (auto it = perfMultiSet.list_begin(); it != perfMultiSet.list_end(); ++it)
        {
            all_values.push_back(*it);
        }
        EXPECT_TRUE(std::is_sorted(all_values.begin(), all_values.end()));
    }

    printf("MultiSet Specific Scenarios test passed\n");
}

